﻿/*
	Copyright (c) 2013 Andrew Meyer

	Permission is hereby granted, free of charge, to any person obtaining a copy of this software
	and associated documentation files (the "Software"), to deal in the Software without
	restriction, including without limitation the right to use, copy, modify, merge, publish,
	distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the
	Software is furnished to do so, subject to the following conditions:

	The above copyright notice and this permission notice shall be included in all copies or
	substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
	BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
	NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
	DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

using System;
using System.Collections.Generic;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Windows;
using System.Windows.Interop;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Media.Media3D;
using System.Xml.Linq;

using Point2D = System.Windows.Point;

namespace Ascend
{
	/// <summary>
	/// Helper class for loading Ascend.SceneNode instances from files or streams.
	/// </summary>
	public static class Loader
	{
		#region Inner Classes
		private class NodeContext
		{
			#region Lifecycle
			public NodeContext()
			{
				ReadContext = new ReadContext();
				ConstructionContext = new ConstructionContext();
			}
			#endregion

			#region Public Properties
			public ReadContext ReadContext
			{
				get;
				private set;
			}

			public ConstructionContext ConstructionContext
			{
				get;
				private set;
			}
			#endregion
		}

		private class ReadContext
		{
			#region Lifecycle
			public ReadContext()
			{
				Vertices = new List<Point3D>();
				Normals = new List<Vector3D>();
				Faces = new List<Face>();
			}
			#endregion

			#region Public Properties
			public List<Point3D> Vertices
			{
				get;
				private set;
			}

			public List<Vector3D> Normals
			{
				get;
				private set;
			}

			public List<Face> Faces
			{
				get;
				private set;
			}
			#endregion
		}

		private struct FaceVertex
		{
			#region Lifecycle
			public FaceVertex(int index, Point3D point)
			{
				_index = index;
				_point = point;
				_normal = INVALID_NORMAL;
				_textureCoordinate = INVALID_UV;
			}
			#endregion

			#region Public Properties
			private int _index;
			public int Index
			{
				get
				{
					return _index;
				}

				set
				{
					_index = value;
				}
			}

			private Point3D _point;
			public Point3D Point
			{
				get
				{
					return _point;
				}

				set
				{
					_point = value;
				}
			}

			private Vector3D _normal;
			public Vector3D Normal
			{
				get
				{
					return _normal;
				}

				set
				{
					_normal = value;
				}
			}

			private Point2D _textureCoordinate;
			public Point2D TextureCoordinate
			{
				get
				{
					return _textureCoordinate;
				}

				set
				{
					_textureCoordinate = value;
				}
			}

			public Tuple<int, Point2D> LookupKey
			{
				get
				{
					return Tuple.Create(Index, TextureCoordinate);
				}
			}
			#endregion
		}

		private class Face
		{
			#region Lifecycle
			public Face()
			{
				Normal = INVALID_NORMAL;
				Vertices = new List<FaceVertex>();
				IndexMap = new Dictionary<int, int>();
			}
			#endregion

			#region Public Properties
			public Vector3D Normal
			{
				get;
				set;
			}

			public List<FaceVertex> Vertices
			{
				get;
				set;
			}

			public Dictionary<int, int> IndexMap
			{
				get;
				private set;
			}

			public bool IsQuad
			{
				get
				{
					return Vertices.Count == 6;
				}
			}
			#endregion
		}

		private class ConstructionContext
		{
			#region Lifecycle
			public ConstructionContext()
			{
				Vertices = new List<Point3D>();
				Normals = new List<Vector3D>();
				TextureCoordinates = new List<Point2D>();
				TriangleIndices = new List<int>();
				VertexAliases = new Dictionary<int, List<int>>();
				SharedVertexMap = new Dictionary<Tuple<int, Point2D>, int>();
				SharedTextureCoordinates = new Dictionary<Tuple<int, Point2D>, bool>();
			}
			#endregion

			#region Public Properties
			public List<Point3D> Vertices
			{
				get;
				private set;
			}

			public List<Vector3D> Normals
			{
				get;
				private set;
			}

			public List<Point2D> TextureCoordinates
			{
				get;
				private set;
			}

			public List<int> TriangleIndices
			{
				get;
				private set;
			}

			public Dictionary<int, List<int>> VertexAliases
			{
				get;
				private set;
			}

			public Dictionary<Tuple<int, Point2D>, int> SharedVertexMap
			{
				get;
				private set;
			}

			public Dictionary<Tuple<int, Point2D>, bool> SharedTextureCoordinates
			{
				get;
				private set;
			}
			#endregion
		}
		#endregion

		#region Constants
		private const double RAD_TO_DEG = 180 / Math.PI;

		private static readonly Vector3D INVALID_NORMAL =
			new Vector3D(double.PositiveInfinity, double.PositiveInfinity, double.PositiveInfinity);

		private static readonly Point2D INVALID_UV =
			new Point2D(double.PositiveInfinity, double.PositiveInfinity);

		private static readonly string[] CompatibleExporterVersions =
		{
			"2.3.0"
		};
		#endregion

		#region Private Members
		private static string _workingDirectory;
		private static Dictionary<string, Bitmap> _textures;
		private static Dictionary<string, Stream> _textureStreams;
		#endregion

		#region Public Methods
		/// <summary>
		/// Loads a hierarchical Ascend scene node from a file.
		/// </summary>
		/// <param name="filename">
		/// The path to the model.
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns the loaded scene node, including any children, textures, or animation properties
		/// defined in the model file.
		/// </returns>
		/// <exception cref="Ascend.LoaderCompatibilityException">
		/// Thrown if the model file was not exported with a compatible version of the Ascend
		/// exporter.
		/// </exception>
		/// <exception cref="Ascend.ModelLoadException">
		/// Thrown if an error is encountered during load.
		/// </exception>
		public static T Load<T>(string filename) where T : ModelSceneNode
		{
			return (T)LoadInternal(filename);
		}

		/// <summary>
		/// Tries to load a hierarchical Ascend scene node from a file and returns whether or not
		/// the load was successful.
		/// </summary>
		/// <param name="filename">
		/// The path to the model.
		/// </param>
		/// <param name="sceneNode">
		/// The loaded scene node (will be null if load failed).
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns true if the load was successful or false if errors were encountered. In the case
		/// that the return value is false, <paramref name="sceneNode"/> will be null.
		/// </returns>
		public static bool TryLoad<T>(string filename, out T sceneNode) where T : ModelSceneNode
		{
			try
			{
				sceneNode = (T)LoadInternal(filename);

				return true;
			}
			catch (ModelLoadException)
			{
				sceneNode = null;

				return false;
			}
		}

		/// <summary>
		/// Loads a hierarchical Ascend scene node from a stream.
		/// </summary>
		/// <param name="stream">
		/// The stream that contains the model file.
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns the loaded scene node, including any children, textures, or animation properties
		/// defined in the model file.
		/// </returns>
		/// <exception cref="Ascend.LoaderCompatibilityException">
		/// Thrown if the model file was not exported with a compatible version of the Ascend
		/// exporter.
		/// </exception>
		/// <exception cref="Ascend.ModelLoadException">
		/// Thrown if an error is encountered during load.
		/// </exception>
		public static T Load<T>(Stream stream) where T : ModelSceneNode
		{
			return (T)LoadInternal(stream);
		}

		/// <summary>
		/// Tries to load a hierarchical Ascend scene node from a stream and returns whether or not
		/// the load was successful.
		/// </summary>
		/// <param name="stream">
		/// The stream that contains the model file.
		/// </param>
		/// <param name="sceneNode">
		/// The loaded scene node (will be null if load failed).
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns true if the load was successful or false if errors were encountered. In the case
		/// that the return value is false, <paramref name="sceneNode"/> will be null.
		/// </returns>
		public static bool TryLoad<T>(Stream stream, out T sceneNode) where T : ModelSceneNode
		{
			try
			{
				sceneNode = (T)LoadInternal(stream);

				return true;
			}
			catch (ModelLoadException)
			{
				sceneNode = null;

				return false;
			}
		}

		/// <summary>
		/// Loads a hierarchical Ascend scene node from a stream.
		/// </summary>
		/// <param name="stream">
		/// The stream that contains the model file.
		/// </param>
		/// <param name="textures">
		/// A bitmap dictionary for resolving texture resources.
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns the loaded scene node, including any children, textures, or animation properties
		/// defined in the model file.
		/// </returns>
		/// <remarks>
		/// The keys in <paramref name="textures"/> must be equivalent to the texture filenames
		/// defined in the model file, including extensions.
		/// </remarks>
		/// <exception cref="Ascend.LoaderCompatibilityException">
		/// Thrown if the model file was not exported with a compatible version of the Ascend
		/// exporter.
		/// </exception>
		/// <exception cref="Ascend.ModelLoadException">
		/// Thrown if an error is encountered during load.
		/// </exception>
		public static T Load<T>(Stream stream, Dictionary<string, Bitmap> textures)
			where T : ModelSceneNode
		{
			return (T)LoadInternal(stream, textures);
		}

		/// <summary>
		/// Tries to load a hierarchical Ascend scene node from a stream and returns whether or not
		/// the load was successful.
		/// </summary>
		/// <param name="stream">
		/// The stream that contains the model file.
		/// </param>
		/// <param name="textures">
		/// A bitmap dictionary for resolving texture resources.
		/// </param>
		/// <param name="sceneNode">
		/// The loaded scene node (will be null if load failed).
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns true if the load was successful or false if errors were encountered. In the case
		/// that the return value is false, <paramref name="sceneNode"/> will be null.
		/// </returns>
		/// <remarks>
		/// The keys in <paramref name="textures"/> must be equivalent to the texture filenames
		/// defined in the model file, including extensions.
		/// </remarks>
		public static bool TryLoad<T>(Stream stream, Dictionary<string, Bitmap> textures,
			out T sceneNode) where T : ModelSceneNode
		{
			try
			{
				sceneNode = (T)LoadInternal(stream, textures);

				return true;
			}
			catch (ModelLoadException)
			{
				sceneNode = null;

				return false;
			}
		}

		/// <summary>
		/// Loads a hierarchical Ascend scene node from a stream.
		/// </summary>
		/// <param name="stream">
		/// The stream that contains the model file.
		/// </param>
		/// <param name="textureStreams">
		/// A stream dictionary for resolving texture resources.
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns the loaded scene node, including any children, textures, or animation properties
		/// defined in the model file.
		/// </returns>
		/// <remarks>
		/// The keys in <paramref name="textureStreams"/> must be equivalent to the texture
		/// filenames defined in the model file, including extensions.
		/// </remarks>
		/// <exception cref="Ascend.LoaderCompatibilityException">
		/// Thrown if the model file was not exported with a compatible version of the Ascend
		/// exporter.
		/// </exception>
		/// <exception cref="Ascend.ModelLoadException">
		/// Thrown if an error is encountered during load.
		/// </exception>
		public static T Load<T>(Stream stream, Dictionary<string, Stream> textureStreams)
			where T : ModelSceneNode
		{
			return (T)LoadInternal(stream, textureStreams);
		}

		/// <summary>
		/// Tries to load a hierarchical Ascend scene node from a stream and returns whether or not
		/// the load was successful.
		/// </summary>
		/// <param name="stream">
		/// The stream that contains the model file.
		/// </param>
		/// <param name="textureStreams">
		/// A stream dictionary for resolving texture resources.
		/// </param>
		/// <param name="sceneNode">
		/// The loaded scene node (will be null if load failed).
		/// </param>
		/// <typeparam name="T">
		/// The type of scene node to load, either Ascend.ModelSceneNode or
		/// Ascend.AnimatedSceneNode.
		/// </typeparam>
		/// <returns>
		/// Returns true if the load was successful or false if errors were encountered. In the case
		/// that the return value is false, <paramref name="sceneNode"/> will be null.
		/// </returns>
		/// <remarks>
		/// The keys in <paramref name="textureStreams"/> must be equivalent to the texture
		/// filenames defined in the model file, including extensions.
		/// </remarks>
		public static bool TryLoad<T>(Stream stream, Dictionary<string, Stream> textureStreams,
			out T sceneNode) where T : ModelSceneNode
		{
			try
			{
				sceneNode = (T)LoadInternal(stream, textureStreams);

				return true;
			}
			catch (ModelLoadException)
			{
				sceneNode = null;

				return false;
			}
		}
		#endregion

		#region Private Methods
		private static ModelSceneNode LoadInternal(string filename)
		{
			try
			{
				_workingDirectory = Path.GetDirectoryName(filename);
				_textures = null;
				_textureStreams = null;

				return LoadFromDocument(XDocument.Load(filename));
			}
			catch (LoaderCompatibilityException)
			{
				throw;
			}
			catch (Exception ex)
			{
				throw new ModelLoadException("Unable to load Ascend model \'" + filename +
					"\'. See the InnerException property for more information.", ex);
			}
		}

		private static ModelSceneNode LoadInternal(Stream stream)
		{
			try
			{
				_workingDirectory = null;
				_textureStreams = null;
				_textures = null;

				return LoadFromDocument(XDocument.Load(stream));
			}
			catch (LoaderCompatibilityException)
			{
				throw;
			}
			catch (Exception ex)
			{
				throw new ModelLoadException("Unable to load Ascend model from stream. " +
					"See the InnerException property for more information.", ex);
			}
		}

		private static ModelSceneNode LoadInternal(Stream stream,
			Dictionary<string, Bitmap> textures)
		{
			try
			{
				_workingDirectory = null;
				_textureStreams = null;
				_textures = textures;

				return LoadFromDocument(XDocument.Load(stream));
			}
			catch (LoaderCompatibilityException)
			{
				throw;
			}
			catch (Exception ex)
			{
				throw new ModelLoadException("Unable to load Ascend model from stream. " +
					"See the InnerException property for more information.", ex);
			}
		}

		private static ModelSceneNode LoadInternal(Stream stream,
			Dictionary<string, Stream> textureStreams)
		{
			try
			{
				_workingDirectory = null;
				_textures = null;
				_textureStreams = textureStreams;

				return LoadFromDocument(XDocument.Load(stream));
			}
			catch (LoaderCompatibilityException)
			{
				throw;
			}
			catch (Exception ex)
			{
				throw new ModelLoadException("Unable to load Ascend model from stream. " +
					"See the InnerException property for more information.", ex);
			}
		}

		private static ModelSceneNode LoadFromDocument(XDocument doc)
		{
			XElement root = doc.Element("Ascend");

			VerifyCompatibility(root);

			return LoadSceneNode((XElement)root.FirstNode);
		}

		private static void VerifyCompatibility(XElement xml)
		{
			if (!CompatibleExporterVersions.Contains(xml.Attribute("ExporterVersion").Value))
			{
				throw new LoaderCompatibilityException("Ascend model file is not compatible with " +
					"this version of Ascend. See the \'ExporterVersion\' attribute in the file's " +
					"top-level \'Ascend\' tag. Compatible exporter version(s): " + 
					string.Join(", ", CompatibleExporterVersions));
			}
		}

		private static ModelSceneNode LoadSceneNode(XElement xml)
		{
			// Create a new context for this node
			NodeContext context = new NodeContext();
			
			ModelSceneNode node;

			// Get SceneNode type
			switch (xml.Name.LocalName)
			{
				case "ModelSceneNode":
					node = new ModelSceneNode();
					break;
				case "AnimatedSceneNode":
					node = new AnimatedSceneNode();
					break;
				default:
					throw new InvalidDataException(
						"Model file does not contain a valid SceneNode.");
			}

			// Read name
			node.Name = xml.Attribute("Name").Value;

			// Load transform
			LoadTransform(node, xml);

			// Load geometry
			LoadMesh(node, context, xml);

			// Load color/texture
			LoadMaterial(node, xml);

			if (node is AnimatedSceneNode)
			{
				// Load animations
				LoadSceneNodeAnimationFrames((AnimatedSceneNode)node, xml);

				// Load armature
				LoadArmature((AnimatedSceneNode)node, context, xml);

				// Load animation definitions
				LoadAnimationDefinitions((AnimatedSceneNode)node, xml);
			}

			// Load children
			foreach (XElement xmlChild in xml.Element("Children").Elements())
			{
				node.Children.Add(LoadSceneNode(xmlChild));
			}

			return node;
		}

		private static void LoadTransform(ModelSceneNode node, XElement xml)
		{
			ObjectPose pose = LoadObjectPose(xml);

			node.Position = new Point3D(pose.X, pose.Y, pose.Z);
			node.Rotation = new Angle3D(pose.AngleX, pose.AngleY, pose.AngleZ);
			node.Scale = new Scale3D(pose.ScaleX, pose.ScaleY, pose.ScaleZ);
		}

		private static void LoadRestTransform(Bone bone, XElement xml)
		{
			ObjectPose pose = LoadObjectPose(xml);

			bone.RestX = pose.X;
			bone.RestY = pose.Y;
			bone.RestZ = pose.Z;

			bone.RestAngleX = pose.AngleX;
			bone.RestAngleY = pose.AngleY;
			bone.RestAngleZ = pose.AngleZ;

			bone.RestScaleX = pose.ScaleX;
			bone.RestScaleY = pose.ScaleY;
			bone.RestScaleZ = pose.ScaleZ;
		}

		private static ObjectPose LoadObjectPose(XElement xml)
		{
			double[] pos = LoadDoubleArray(xml.Attribute("Position"));
			double[] rot = LoadDoubleArray(xml.Attribute("Rotation"));
			double[] scl = LoadDoubleArray(xml.Attribute("Scale"));

			return new ObjectPose
			{
				X = pos[0],
				Y = pos[1],
				Z = pos[2],

				AngleX = rot[0] * RAD_TO_DEG,
				AngleY = rot[1] * RAD_TO_DEG,
				AngleZ = rot[2] * RAD_TO_DEG,

				ScaleX = scl[0],
				ScaleY = scl[1],
				ScaleZ = scl[2],
			};
		}

		private static void LoadMaterial(ModelSceneNode node, XElement xml)
		{
			if (xml.Attribute("Texture") != null &&
				TryLoadTexture(node, xml.Attribute("Texture").Value))
			{
				return;
			}

			// If texture loading failed, set color
			double[] col = LoadDoubleArray(xml.Attribute("Color"));

			node.Model.Material = new DiffuseMaterial(new SolidColorBrush(
				new System.Windows.Media.Color
				{
					ScR = (float)col[0],
					ScG = (float)col[1],
					ScB = (float)col[2],
					ScA = (float)col[3]
				}
			));
		}

		private static bool TryLoadTexture(ModelSceneNode node, string texture)
		{
			ImageSource img = null;

			// Load texture from file path, bitmap resource, or stream
			if (_workingDirectory != null)
			{
				img = LoadTextureFromPath(texture);
			}
			else if (_textures != null && _textures.ContainsKey(texture))
			{
				img = LoadTextureFromBitmap(_textures[texture]);
			}
			else if (_textureStreams != null && _textureStreams.ContainsKey(texture))
			{
				img = LoadTextureFromStream(_textureStreams[texture]);
			}

			if (img != null)
			{
				node.Model.Material = new DiffuseMaterial(new ImageBrush(img)
				{
					TileMode = TileMode.Tile,
					ViewportUnits = BrushMappingMode.Absolute,
				});

				return true;
			}

			return false;
		}

		private static BitmapSource LoadTextureFromPath(string texture)
		{
			string texturePath = Path.Combine(_workingDirectory, texture);

			if (!File.Exists(texturePath))
			{
				return null;
			}

			return new BitmapImage(new Uri(texturePath, UriKind.Relative));
		}

		[DllImport("gdi32.dll")]
		private static extern bool DeleteObject(IntPtr hObject);

		private static BitmapSource LoadTextureFromBitmap(Bitmap bitmap)
		{
			BitmapSource src = null;
			IntPtr hBitmap = bitmap.GetHbitmap();

			try
			{
				src = Imaging.CreateBitmapSourceFromHBitmap(hBitmap, IntPtr.Zero, Int32Rect.Empty,
					BitmapSizeOptions.FromEmptyOptions());
			}
			finally
			{
				DeleteObject(hBitmap);
			}

			return src;
		}

		private static BitmapSource LoadTextureFromStream(Stream stream)
		{
			BitmapImage img = new BitmapImage();
			img.BeginInit();
			img.CacheOption = BitmapCacheOption.OnLoad;
			img.StreamSource = stream;
			img.EndInit();

			return img;
		}

		private static void LoadMesh(ModelSceneNode node, NodeContext context, XElement xml)
		{
			// Load vertex locations and normals
			LoadVertexData(context, xml);

			// Load face indices and texture coordinates
			LoadFaceData(context, xml);

			node.Model = new GeometryModel3D
			{
				Geometry = ConstructMesh(context, xml)
			};
		}

		private static void LoadVertexData(NodeContext context, XElement xml)
		{
			XElement xmlVertices = xml.Element("Vertices");

			foreach (XElement xmlVert in xmlVertices.Elements("Vertex"))
			{
				context.ReadContext.Vertices.Add(LoadPoint3D(xmlVert.Attribute("Point")));

				// Load vertex normal if there is one
				if (xmlVert.Attribute("Normal") != null)
				{
					context.ReadContext.Normals.Add(LoadVector3D(xmlVert.Attribute("Normal")));
				}
			}
		}

		private static void LoadFaceData(NodeContext context, XElement xml)
		{
			XElement xmlFaces = xml.Element("Faces");

			foreach (XElement xmlFace in xmlFaces.Elements("Face"))
			{
				Face face = new Face();

				// Check for face normal
				if (xmlFace.Attribute("Normal") != null)
				{
					face.Normal = LoadVector3D(xmlFace.Attribute("Normal"));
				}

				// Load indices
				foreach (XElement xmlFaceVertex in xmlFace.Elements("FaceVertex"))
				{
					LoadFaceVertex(face, context, xmlFaceVertex);
				}

				// Convert any quad faces to two triangular faces
				if (face.Vertices.Count == 4)
				{
					face.Vertices = new List<FaceVertex>
					{
						face.Vertices[0], face.Vertices[1], face.Vertices[2],
						face.Vertices[2], face.Vertices[3], face.Vertices[0]
					};
				}

				context.ReadContext.Faces.Add(face);
			}
		}

		private static void LoadFaceVertex(Face face, NodeContext context, XElement xml)
		{
			int index = LoadInteger(xml.Attribute("Index"));
			FaceVertex vertex = new FaceVertex(index, context.ReadContext.Vertices[index]);
			
			// Set normal to face's normal (if any) or vertex normal (if any)
			if (face.Normal != INVALID_NORMAL)
			{
				// If a face normal exists, it has precedence over a vertex normal
				vertex.Normal = face.Normal;
			}
			else if (vertex.Index < context.ReadContext.Normals.Count)
			{
				vertex.Normal = context.ReadContext.Normals[index];
			}

			// Check for texture coordinate
			if (xml.Attribute("UV") != null)
			{
				vertex.TextureCoordinate = LoadPoint2D(xml.Attribute("UV"));

				// Update shared texture coordinates
				Tuple<int, Point2D> key = vertex.LookupKey;

				if (context.ConstructionContext.SharedTextureCoordinates.ContainsKey(key))
				{
					// Any texture coordinate encountered more than once can be shared
					context.ConstructionContext.SharedTextureCoordinates[key] = true;
				}
				else
				{
					// Texture coordinate cannot be shared until it is encountered at least twice
					context.ConstructionContext.SharedTextureCoordinates.Add(key, false);
				}
			}

			face.Vertices.Add(vertex);
		}

		private static MeshGeometry3D ConstructMesh(NodeContext context, XElement xml)
		{
			// Process faces
			foreach (Face face in context.ReadContext.Faces)
			{
				ProcessFace(face, context);
			}

			// Construct mesh from processed data
			MeshGeometry3D mesh = new MeshGeometry3D();

			mesh.Positions = new Point3DCollection(context.ConstructionContext.Vertices);
			mesh.TriangleIndices = new Int32Collection(context.ConstructionContext.TriangleIndices);

			if (context.ConstructionContext.Normals.Any())
			{
				mesh.Normals = new Vector3DCollection(context.ConstructionContext.Normals);
			}

			if (context.ConstructionContext.TextureCoordinates.Any())
			{
				mesh.TextureCoordinates =
					new PointCollection(context.ConstructionContext.TextureCoordinates);
			}

			return mesh;
		}

		private static void ProcessFace(Face face, NodeContext context)
		{
			for (int i = 0; i < face.Vertices.Count; i++)
			{
				// Process vertex as shared or non-shared
				if (CanShareVertex(i, face, context))
				{
					ProcessSharedVertex(i, face, context);
				}
				else
				{
					ProcessNonSharedVertex(i, face, context);
				}
			}
		}

		private static bool CanShareVertex(int indexInFace, Face face, NodeContext context)
		{
			Tuple<int, Point2D> key = face.Vertices[indexInFace].LookupKey;
			Point2D uv = key.Item2;

			// A vertex can be shared if it does not use a face normal and its texture coordinate
			// (if any) can be shared at the given vertex
			return face.Normal == INVALID_NORMAL &&
				(uv == INVALID_UV || context.ConstructionContext.SharedTextureCoordinates[key]);
		}

		private static void ProcessSharedVertex(int indexInFace, Face face, NodeContext context)
		{
			Tuple<int, Point2D> key = face.Vertices[indexInFace].LookupKey;

			if (context.ConstructionContext.SharedVertexMap.ContainsKey(key))
			{
				context.ConstructionContext.TriangleIndices.Add(
					context.ConstructionContext.SharedVertexMap[key]);
			}
			else
			{
				AddNewVertex(indexInFace, face, true, context);
			}
		}

		private static void ProcessNonSharedVertex(int indexInFace, Face face,
			NodeContext context)
		{
			if (face.IsQuad)
			{
				HandleQuadFaceVertex(indexInFace, face, context);
			}
			else
			{
				AddNewVertex(indexInFace, face, false, context);
			}
		}

		private static void HandleQuadFaceVertex(int indexInFace, Face face,
			NodeContext context)
		{
			/*
			 * Since quad faces are converted into two triangular faces, indexed as follows,
			 * 
			 *			0	1
			 *		  5 O---O
			 *			|\  |
			 *			| \ |
			 *			O---O 2
			 *			4	3
			 * 
			 * vertex 0 can be shared with vertex 5, and vertex 2 can be shared with vertex 3
			 */

			int newVertexIdx = context.ConstructionContext.Vertices.Count;

			if (indexInFace == 0 || indexInFace == 2)
			{
				// Store vertex index
				face.IndexMap[indexInFace] = newVertexIdx;
			}
			else if (indexInFace == 3)
			{
				// Reuse vertex 2
				context.ConstructionContext.TriangleIndices.Add(face.IndexMap[2]);

				// Skip adding a new vertex
				return;
			}
			else if (indexInFace == 5)
			{
				// Reuse vertex 0
				context.ConstructionContext.TriangleIndices.Add(face.IndexMap[0]);

				// Skip adding a new vertex
				return;
			}

			AddNewVertex(indexInFace, face, false, context);
		}

		private static void AddNewVertex(int indexInFace, Face face, bool shared,
			NodeContext context)
		{
			FaceVertex vertex = face.Vertices[indexInFace];
			int newVertexIdx = context.ConstructionContext.Vertices.Count;

			// Add vertex
			context.ConstructionContext.Vertices.Add(vertex.Point);
			context.ConstructionContext.TriangleIndices.Add(newVertexIdx);

			// Add corresponding normal
			Vector3D normal = vertex.Normal;

			if (normal != INVALID_NORMAL)
			{
				context.ConstructionContext.Normals.Add(normal);
			}

			// Add corresponding texture coordinate
			Point2D uv = vertex.TextureCoordinate;

			if (uv != INVALID_UV)
			{
				context.ConstructionContext.TextureCoordinates.Add(uv);
			}

			// Add alias
			if (context.ConstructionContext.VertexAliases.ContainsKey(vertex.Index))
			{
				context.ConstructionContext.VertexAliases[vertex.Index].Add(newVertexIdx);
			}
			else
			{
				context.ConstructionContext.VertexAliases.Add(vertex.Index,
					new List<int> { newVertexIdx });
			}

			// Add shared vertex entry
			if (shared)
			{
				context.ConstructionContext.SharedVertexMap.Add(vertex.LookupKey, newVertexIdx);
			}
		}

		private static void LoadSceneNodeAnimationFrames(AnimatedSceneNode node, XElement xml)
		{
			if (xml.Element("Frames") == null)
			{
				return;
			}

			foreach (XElement xmlFrame in xml.Element("Frames").Elements("Frame"))
			{
				node.AnimationFrames.Add(new AnimationFrame
				{
					ModelPose = LoadObjectPose(xmlFrame)
				});
			}
		}

		private static void LoadBoneAnimationFrames(Bone bone, Armature arm, XElement xml)
		{
			if (xml.Element("Frames") == null)
			{
				return;
			}

			int frameNumber = 0;
			foreach (XElement xmlFrame in xml.Element("Frames").Elements("Frame"))
			{
				if (!SkinHasFrame(arm.Skin, frameNumber))
				{
					// If skin does not have the frame at this point,
					// there are no rigid animations for it; this frame
					// will only include bone poses.
					arm.Skin.AnimationFrames.Add(new AnimationFrame());
				}

				// Set the bone pose for this frame
				arm.Skin.AnimationFrames[frameNumber].BonePoses.Add(bone, LoadObjectPose(xmlFrame));

				frameNumber++;
			}
		}

		private static bool SkinHasFrame(AnimatedSceneNode skin, int frameNumber)
		{
			return frameNumber < skin.AnimationFrames.Count();
		}

		private static void LoadAnimationDefinitions(AnimatedSceneNode node, XElement xml)
		{
			if (xml.Element("Animations") == null)
			{
				return;
			}

			foreach (XElement xmlAnim in xml.Element("Animations").Elements("Animation"))
			{
				node.DefineAnimation(xmlAnim.Attribute("Name").Value,
					LoadInteger(xmlAnim.Attribute("Start")),
					LoadInteger(xmlAnim.Attribute("End")));
			}
		}

		private static void LoadArmature(AnimatedSceneNode node, NodeContext context, XElement xml)
		{
			XElement xmlArm = xml.Element("Armature");

			if (xmlArm == null)
			{
				return;
			}

			node.Armature = new Armature();

			// Read name
			node.Armature.Name = xmlArm.Attribute("Name").Value;

			// Load root Bones
			foreach (XElement xmlBone in xmlArm.Element("RootBones").Elements())
			{
				node.Armature.RootBones.Add(LoadBone(node.Armature, context, xmlBone));
			}
		}

		private static Bone LoadBone(Armature arm, NodeContext context, XElement xml)
		{
			Bone bone = new Bone();

			// Read name
			bone.Name = xml.Attribute("Name").Value;

			// Load and set rest transform
			LoadRestTransform(bone, xml);
			bone.Rest();

			// Load vertex influences
			LoadBoneInfluences(bone, context.ConstructionContext.VertexAliases, xml);

			// Load animation frames
			LoadBoneAnimationFrames(bone, arm, xml);

			// Load children
			foreach (XElement xmlChild in xml.Element("Children").Elements())
			{
				if (xmlChild.Name == "Bone")
				{
					bone.Children.Add(LoadBone(arm, context, xmlChild));
				}
				else
				{
					bone.RigidAttachments.Add(LoadSceneNode(xmlChild));
				}
			}

			return bone;
		}

		private static void LoadBoneInfluences(Bone bone, Dictionary<int, List<int>> vertexAliases,
			XElement xml)
		{
			XElement xmlInfluences = xml.Element("Influences");

			foreach (XElement xmlInf in xmlInfluences.Elements("Influence"))
			{
				VertexInfluence inf = new VertexInfluence(
					LoadDouble(xmlInf.Attribute("Weight")),
					vertexAliases[LoadInteger(xmlInf.Attribute("Vertex"))]);

				bone.VertexInfluences.Add(inf);
			}
		}

		private static Point2D LoadPoint2D(XAttribute xmlAttr)
		{
			double[] val = LoadDoubleArray(xmlAttr);

			return new Point2D(val[0], val[1]);
		} 

		private static Point3D LoadPoint3D(XAttribute xmlAttr)
		{
			double[] val = LoadDoubleArray(xmlAttr);

			return new Point3D(val[0], val[1], val[2]);
		}

		private static Vector3D LoadVector3D(XAttribute xmlAttr)
		{
			double[] val = LoadDoubleArray(xmlAttr);

			return new Vector3D(val[0], val[1], val[2]);
		}

		private static double[] LoadDoubleArray(XAttribute xmlAttr)
		{
			return xmlAttr.Value.Split().Select(val => double.Parse(val)).ToArray();
		}

		private static int[] LoadIntegerArray(XAttribute xmlAttr)
		{
			return xmlAttr.Value.Split().Select(val => int.Parse(val)).ToArray();
		}

		private static double LoadDouble(XAttribute xmlAttr)
		{
			return double.Parse(xmlAttr.Value);
		}

		private static int LoadInteger(XAttribute xmlAttr)
		{
			return int.Parse(xmlAttr.Value);
		}
		#endregion
	}
}
